package com.yulongtian.algorithms.binarysearch01;

/**
 * https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/
 * 二分查找 可
 *
 * @author yulongTian
 * @create 2023-02-07 11:29
 */
public class Test09 {
    public static void main(String[] args) {
        int[][] grid = {
                {4, 3, 2, -1},
                {3, 2, 1, -1},
                {-1, -1, -1, -2},
                {-1, -1, -2, -3}
        };
//        int[][] grid = {
//                {3, 2},
//                {1, 0}
//        };
        System.out.println(countNegatives(grid));
    }

    public static int countNegatives(int[][] grid) {
        int n = grid[0].length;
        int m = grid.length;
        int ans = 0;
        //每行开始的遍历起始索引
        int index = n - 1;
        for (int i = 0; i < m; i++) {
            //倒序遍历
            for (int j = index; j >= 0; j--) {
                //遇到非负数
                if (grid[i][j] >= 0) {
                    if (j != n - 1) {
                        index = j + 1;
                    }
                    if (j != n - 1) {
                        ans += n - index;
                    }
                    break;
                }
                //以下每行都是负数 可以提前结束
                if (j == 0) {
                    ans += (m - i) * n;
                    i=m;
                    break;
                }
            }
        }
        return ans;
    }

//    //二分查找  可 O(m lgn)
//    public static int countNegatives(int[][] grid) {
//        int n = grid[0].length;
//        int ans = 0;
//        for (int[] ints : grid) {
//            int left = 0;
//            int right = n - 1;
//            while (left <= right) {
//                int mid = left + (right - left) / 2;
//                if (ints[mid] >= 0) {
//                    left = mid + 1;
//                } else {
//                    right = mid - 1;
//                }
//            }
//            ans += n - left;
//        }
//        return ans;
//    }

}
